/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  //找到数组中第一个nums[i]<nums[i+1]的位置
  let i = nums.length - 2
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--
  }

  //如果i>=0
  if (i >= 0) {
    //找到第一个大于nums[i]的索引
    let j = nums.length - 1
    while (j >= 0 && nums[j] <= nums[i]) {
      j--
    }
    // 交换nums[i]和nums[j]的位置
    [nums[i], nums[j]] = [nums[j], nums[i]]
  }

  //将i+1道nums.length-1的数组元素逆转
  nums = reverse(i + 1, nums)
}

function reverse(start, nums) {
  let left = start, right = nums.length - 1

  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]]
    left++
    right--
  }
}